/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhong
 *
 */
public class SortArrayByParityII {
	public int[] sortArrayByParityII(int[] A) {
		int j = A.length - 1;
		List<Integer> toSwap1 = new ArrayList<>();
		List<Integer> toSwap0 = new ArrayList<>();
		for (int i = 0; i < A.length; i++) {
			if (A[i] % 2 != i % 2) {
				if (i % 2 == 0) {
					toSwap0.add(i);
				} else {
					toSwap1.add(i);
				}
			}
		}
		int m = toSwap0.size();
		for (int i = 0; i < m; i++) {
			swap(A, toSwap0.get(i), toSwap1.get(i));
		}

		return A;
	}

	private void swap(int[] a, Integer integer, Integer integer2) {
		int tmp = a[integer];
		a[integer] = a[integer2];
		a[integer2] = tmp;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] a = { 4, 2, 5, 7 };
		a = new SortArrayByParityII().sortArrayByParityII(a);
		for (int i : a) {
			System.out.println(i);

		}
	}

}
